from cmath import inf
from collections import deque
n, m = map(int, input().split())
grid = [[i for i in input()] for _ in range(n)]
directions = [(1,0),(0,1),(-1,0),(0,-1)]
def solve(n, m, grid):
for i in range(n):
for j in range(m):
if grid[i][j] == "S":
start = (i, j)
queue = deque()
for dr, dc in directions:
queue.append(((start, (dr, dc), 0)))
visited = [[inf for _ in range(m)] for _ in range(n)]
while queue:
pos, dir, turns = queue.popleft()
if grid[pos[0]][pos[1]] == "T" and turns <= 2:
return True
if turns > 2:
continue
for dr, dc in directions:
nr, nc = pos[0] + dr, pos[1] + dc
if 0<=nr<n and 0<=nc<m and grid[nr][nc] != "*" and visited[nr][nc] >= turns+1:
if dir == (dr, dc):
queue.append(((nr, nc), (dr, dc), turns))
visited[nr][nc] = turns
elif turns < 2:
queue.append(((nr, nc), (dr, dc), turns + 1))
visited[nr][nc] = turns + 1
return False
if solve(n, m, grid):
print("YES")
else:
print("NO")#include <bits/stdc++.h>
using namespace std;
int n, m,sx,sy,ex,ey;
vector<vector<char>> a;
bool f;
bool vst[1002][1002][4][26];
bool valid(int i,int j){return i>0&&j>0&&i<=n&&j<=m&&a[i][j]!='*';}
void dfs(int i=sx,int j=sy,int turn=-1,char last='X'){
// cout <<i<<' '<<j<<' '<<turn<<'\n';
if (turn >2||vst[i][j][turn][last-'A'])return;
if (i==ex&&j==ey){
f=1;
return ;
}
vst[i][j][turn][last-'A']=1;
if (valid(i+1,j))dfs(i+1,j,turn +(last!='D'),'D');
if (valid(i-1,j))dfs(i-1,j,turn +(last!='U'),'U');
if (valid(i,j+1))dfs(i,j+1,turn +(last!='R'),'R');
if (valid(i,j-1))dfs(i,j-1,turn +(last!='L'),'L');
}
int main() {
cin >> n >> m;
a.resize(n + 2, vector<char>(m + 2));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j]=='S')sx=i,sy=j;
if (a[i][j]=='T')ex=i,ey=j;
}
dfs(sx,sy,-1,'X');
cout <<(f?"YES":"NO");
}17. Letter Combinations of a Phone Number | 5. Longest Palindromic Substring |
3. Longest Substring Without Repeating Characters | 1312. Minimum Insertion Steps to Make a String Palindrome |
1092. Shortest Common Supersequence | 1044. Longest Duplicate Substring |
1032. Stream of Characters | 987. Vertical Order Traversal of a Binary Tree |
952. Largest Component Size by Common Factor | 212. Word Search II |
174. Dungeon Game | 127. Word Ladder |
123. Best Time to Buy and Sell Stock III | 85. Maximal Rectangle |
84. Largest Rectangle in Histogram | 60. Permutation Sequence |
42. Trapping Rain Water | 32. Longest Valid Parentheses |
Cutting a material | Bubble Sort |
Number of triangles | AND path in a binary tree |
Factorial equations | Removal of vertices |
Happy segments | Cyclic shifts |
Zoos | Build a graph |
Almost correct bracket sequence | Count of integers |